1. Field of the Invention
The present invention relates to the placement of components for performing a function, or more particularly, to a system and method of placing components on a chip for performing a function in order to minimize wire congestion and wire length.
2. Description of Related Art
Electronic circuits are commonly used in today""s marketplace to produce needed results or provided valuable information. Typically, electronic circuits will utilize several embedded functions in order to produce a particular result. For example, a public key encryption circuit may utilize several shifting functions, adding functions, and flip-flop functions in order to produce an encrypted result. The components that perform these functions (e.g., shifting, adding, and flip-flop) are typically arranged on a chip such that information is passed from function to function in a pipeline (or serial) fashion. In other words, each function is laid out parallel to the other functions so the component adapted to receive the least-significant bit (LSB) of the first function is immediately adjacent to the component adapted to receive the LSB of the second function and the component adapted to receive the most-significant bit (MSB) of the first function is immediately adjacent to the component adapted to receive the MSB of the second function. This allows the data associated with certain bits (e.g., bit 0, bit 1, etc.) to flow serially from function to function.
A drawback of this type of component arrangement is that it becomes problematic when a large number of data bits (e.g., thousands of data bits) are being manipulated to produce a certain result. This is because data does not only move in a vertical direction (i.e., from function to function), but also in a horizontal direction (i.e., from component to component within a single function). For example, in a shifter, data from bit 7 may need to be xe2x80x9cshiftedxe2x80x9d to bit 8. Or more problematic, data from bit 7 may need to be xe2x80x9cshiftedxe2x80x9d to bit 1024. To enable a function to move data horizontally (i.e., from component to component within a single function), horizontally-oriented wires are used to interconnect the various components of a function. This results in either wires spanning over large distance (e.g., from bit 0 to bit 1024), or a large number of wires spanning over smaller distances (e.g., from bit 0 to bit 1, from bit 1 to bit 2, etc.)xe2x80x94the former causing wire congestion and the latter causing slow response time (e.g., moving data one bit at a time). This requires the designer of to choose between circuit size (e.g., a larger circuit may be need if wires are congested) and circuit speed.
Thus, a need exists, and it would be desirable to have a system and method of placing components on a chip for performing a function that minimizes wire congestion and wire length without substantially decreasing circuit speed.
The present invention provides a system and method of placing components on a chip for performing a function in order to minimize wire length and wire congestion. In a preferred embodiment of the present invention, a plurality of components, which are adapted to receive a plurality of bits, are arranged in lines that are substantially parallel to one another. Within each line, the components are arranged such that the component adapted to receive the least-significant bit (LSB) for that line is positioned at a first end of the line, and a component adapted to receive the most-significant bit (MSB) for that line is positioned at a second end of the line. The lines are then oriented such that the first end of all odd numbered lines are adjacent the second end of all even-numbered lines (i.e., in a serpentine fashion). The plurality of components are then electrically connected.
In one embodiment of the present invention, each component is electrically connected to a next-least-significant component and/or a similarly-positioned component from the next-least-significant similarly-oriented line. In another embodiment of the present invention, each component is electrically connected to a next-most-significant component and/or a similarly-positioned component from the next-most-significant similarly-oriented line.
The present invention further provides a system and method of placing components on a chip for performing multiple functions (e.g., a primary and secondary function). Specifically, the lines of components for performing the secondary function are arranged in a serpentine fashion and interlaced amongst the lines of components for performing the primary function. A plurality of inter-function wires are then arranged, electrically connecting the output of the primary function""s components to the input of the secondary function""s components, in order to minimize wire length and wire congestion. In another embodiment of the present invention, the secondary function further includes multiple sub-functions.
A more complete understanding of the system and method of placing components for minimizing wire congestion and wire length will be afforded to those skilled in the art, as well as a realization of additional advantages and objects thereof, by a consideration of the following detailed description of the preferred embodiment. Reference will be made to the appended sheets of drawings which will first be described briefly.